package com.murphy.algorithm.sort;

/**
 * 快速排序
 * @author dongsufeng
 * @date 2020/9/16 17:37
 * @version 1.0
 */
public class QuickSort {
	/**
	 *
	 * @param items 数组
	 * @param l 左边指针
	 * @param r 右边指针
	 */
	public static void sort(int [] items,int l,int r){
		//当左边指针>=右边指针时停止
		if (l>=r){
			return;
		}
		//确定基准数据位置，按技术将数组分为：小于基数的左侧数组、基数、大于基数的右侧数组
		int i = getIndex(items,l,r);
		//重复左侧数组
		sort(items,l,i-1);
		//重复右侧数组
		sort(items,i+1,r);
	}
	public static int getIndex(int [] items,int l ,int r){
		//取第一个作为基准
		int temp = items[l];
		//左右指针指向同一下标时停止
		while (l<r){
			//从右侧开始对比基准值，如果小于基准停止循环，放入基准值左侧
			while (l<r && items[r]>=temp){
				--r;
			}
			items[l]=items[r];
			//从左侧开始对比基准值，如果大于基准停止循环，放入基准值右侧
			while (l<r && items[l]<=temp){
				++l;
			}
			items[r]=items[l];
		}
		//最终左右指针指向一个空下标，将基准值放入，返回下标
		//此时整个数组分为：小于基准值的左侧部分，基准值，大于基准值的右侧部分
		items[l]=temp;
		return l;
	}

	public static void main(String[] args) {
		int [] items={2,1,4,5,6,3,7,9,8};
		QuickSort.sort(items,0,items.length-1);
		for (int item : items){
			System.out.println(item);
		}
	}
}
